package com.lyz.dataStructure.LeetCode.dongtaiguihua;

import java.util.Scanner;

/**
 *@Author:759057893@qq.com Lyz
 *@Date: 2019/7/21 20:59
 *@Description:
 **/
/*
leetcode 279  完全平方数
 */
public class Soulution7 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        System.out.println(numSquares(n));
    }

    public static int numSquares(int n){
        int[] dp = new int[n+1];
        dp[0] = 0;
        dp[1] =1;

        for(int i =2;i<=n;i++){
            int min = Integer.MAX_VALUE;
            for(int j =1; j*j<=i;j++){
                if(j*j==i){
                    min =1 ;
                    break;
                }
                min = Math.min(min,dp[j*j]+dp[i-j*j]);
            }
            dp[i] =min;
        }
        return dp[n];
    }
}
